Communication networks take many forms for interconnecting a source node to a destination node. With the advent of the Internet and its exponential growth, communication networks are increasing in size and complexity and moving toward using optical networks to provide very high speed interconnection bandwidth of the order of gigabits to terabits per second. An optical network generally consists of optical switch nodes and fiber optic interconnection links between nodes arranged in a general mesh topology. Due to the size and complexity of many communication networks, routing paths between numerous source and destination nodes that meet various constraints is a difficult problem. Some of the constraints considered, for example, are performance, in terms of path distance and bandwidth, costs, such as fiber and equipment costs, and link and node failure probabilities.
A physical network is typically modeled by converting point to point links to edges in a directed or undirected graph with nodes in the graph corresponding to optical switches and source and destination points of the physical system. The nodes and edges may be labeled with a metric, typically performance and costs, as a constraining parameter on the link or node. The problem of finding routing paths in a physical network corresponds to finding paths in the directed or undirected graph. Failure probabilities have been typically accounted for by routing two paths, a primary path and a backup path, and making both paths as disjoint as possible.
One approach to finding a node/edge disjoint pair of paths between a given node pair in a directed or undirected graph is to use a technique such as described by Suurballe, “Disjoint paths in a Network,” Networks, Vol. 4, pp. 125-145, 1974. Since many characteristics of physical networks are not easily abstracted to a graph, using techniques such as described by Suurballe are not adequate, especially when considering failure potentials in physical networks.